home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / dsp / dspgroup / fft32010.arc / PROGRAM.5 < prev    next >
Encoding:
Text File  |  1984-11-13  |  11.9 KB  |  607 lines
  1.       IDT 'FFT4-3'
  2. *
  3. *    Cooley-Tukey Radix-4, DIF FFT Program
  4. *
  5. *    Three radix-4 butterflies.
  6. *    Complex input data - size limited only by program memory availability.
  7. *    Uses table lookup of twiddle factors.
  8. *    No scaling is done on intermediate values in the program.
  9. *    External data RAM is addressed via peripheral I/O instructions.
  10. *        An address counter is required and is loaded by a write
  11. *        to port 0.  Data is read from and written to port 1.
  12. *    Data in the external RAM assumes complex data with corresponding
  13. *        real and imaginary data values in consecutive locations.
  14. *
  15. * N is the size of the transform (N = 4**M).
  16. N EQU 64
  17. M EQU 3
  18. *
  19. * Data memory allocation.
  20. *
  21. XI     EQU 0        * Data values for butterfly
  22. YI     EQU 1
  23. XI1    EQU 2
  24. YI1    EQU 3
  25. XI2    EQU 4
  26. YI2    EQU 5
  27. XI3    EQU 6
  28. YI3    EQU 7
  29. I      EQU 8        * Data indices
  30. I1     EQU 9
  31. I2     EQU 10
  32. I3     EQU 11
  33. CO1    EQU 12        * Twiddle factor coefficients
  34. CO2    EQU 13
  35. CO3    EQU 14
  36. SI1    EQU 15
  37. SI2    EQU 16
  38. SI3    EQU 17
  39. N1     EQU 18        * Increment to I
  40. N2     EQU 19        * Index separation
  41. IA     EQU 20        * Index to twiddle factors
  42. IE     EQU 21        * Increment to IA
  43. J      EQU 22        * Counters
  44. K      EQU 23
  45. R1     EQU 24        * Temporaries
  46. R2     EQU 25
  47. S1     EQU 26
  48. S2     EQU 27
  49. R3     EQU 28
  50. R4     EQU 29
  51. S3     EQU 30
  52. S4     EQU 31
  53. XJ     EQU 32
  54. YJ     EQU 33
  55. TEMP   EQU 34
  56. T      EQU 35
  57. HOLDN  EQU 36        * Contains the value N
  58. QUARTN EQU 37        * Contains the value N/4
  59. ONE    EQU 38        * Contains the value 1
  60. TABLE  EQU 39        * Location of coefficient table
  61. JT     EQU 40
  62. C21    EQU 41        * Contains value .707106778
  63. *
  64. * Begin program memory section.
  65. *
  66.       AORG 0
  67. START      LDPK 0
  68.       LACK 1
  69.       SACL IE          * Initialize IE = 1
  70.       SACL ONE
  71.       LT   ONE
  72.       MPYK SINE
  73.       PAC
  74.       SACL TABLE          * Save location of sine table
  75.       SUB  ONE
  76.       TBLR C21          * Read coefficient for W = J
  77.       MPYK N
  78.       PAC
  79.       SACL HOLDN
  80.       SACL N2          * Initialize N2 = N
  81.       LAC  HOLDN,14
  82.       SACH QUARTN          * QUARTN = N/4
  83.       LARK AR1,M-1          * AR0 contains K value
  84. KLOOP         LAC  N2
  85.          SACL N1          * N1 = N2
  86.          LAC  N2,13
  87.          SACH N2,1          * N2 = N2/4
  88.          SACH JT          * JT = N2/2
  89. ********************************************************************
  90. *
  91. *  Special butterfly for theta = 0.
  92. *
  93. ********************************************************************
  94.         LARP 0
  95.         LAR  AR0,IE      * Loop counter - repeat loop IE times
  96.         MAR  *-
  97.         ZAC
  98.         SACL I         * I = 0.
  99. ZERO        LAC  I
  100.         ADD  N2,1
  101.         SACL I1         * I1 = I + N2
  102.         ADD  N2,1
  103.         SACL I2         * I2 = I1 + N2
  104.         ADD  N2,1
  105.         SACL I3         * I3 = I2 + N2
  106. *
  107. * Read in four data values.
  108. *
  109.         OUT  I,PA0
  110.         IN     XI,PA1
  111.         IN     YI,PA1
  112.         OUT  I1,PA0
  113.         IN     XI1,PA1
  114.         IN     YI1,PA1
  115.         OUT  I2,PA0
  116.         IN     XI2,PA1
  117.         IN     YI2,PA1
  118.         OUT  I3,PA0
  119.         IN     XI3,PA1
  120.         IN     YI3,PA1
  121. *
  122. * Start butterfly.
  123. *
  124.         LAC  XI
  125.         ADD  XI2
  126.         SACL R1        * R1 = X(I) + X(I2)
  127.         SUB  XI2,1
  128.         SACL R2        * R2 = X(I) - X(I2)
  129.         LAC  XI1
  130.         ADD  XI3
  131.         SACL R3        * R3 = X(I1) + X(I3)
  132.         ADD  R1
  133.         SACL XI        * X(I) = R1 + R3
  134.         SUB  R3,1
  135.         SACL XI2        * X(I2) = R1 - R3
  136. *
  137.         LAC  YI
  138.         ADD  YI2
  139.         SACL R1        * R1 = Y(I) + Y(I2)
  140.         SUB  YI2,1
  141.         SACL R4        * R4 = Y(I) - Y(I2)
  142.         LAC  YI1
  143.         ADD  YI3
  144.         SACL R3        * R3 = Y(I1) + Y(I3)
  145.         ADD  R1
  146.         SACL YI        * Y(I) = R1 + R3
  147.         SUB  R3,1
  148.         SACL YI2        * Y(I2) = R1 - R3
  149. *
  150.         LAC  XI1
  151.         SUB  XI3
  152.         SACL R1        * R1 = X(I1) - X(I3)
  153.         LAC  YI1
  154.         SUB  YI3
  155.         SACL R3        * R3 = Y(I1) - Y(I3)
  156.         ADD  R2
  157.         SACL XI1        * X(I1) = R2 + R3
  158.         SUB  R3,1
  159.         SACL XI3        * X(I3) = R2 - R3
  160.         LAC  R4
  161.         SUB  R1
  162.         SACL YI1        * Y(I1) = R4 - R1
  163.         ADD  R1,1
  164.         SACL YI3        * Y(I3) = R4 + R1
  165. *
  166. * Output four results.
  167. *
  168.         OUT  I,PA0
  169.         OUT  XI,PA1
  170.         OUT  YI,PA1
  171.         OUT  I1,PA0
  172.         OUT  XI1,PA1
  173.         OUT  YI1,PA1
  174.         OUT  I2,PA0
  175.         OUT  XI2,PA1
  176.         OUT  YI2,PA1
  177.         OUT  I3,PA0
  178.         OUT  XI3,PA1
  179.         OUT  YI3,PA1
  180. *
  181.         LAC  I
  182.         ADD  N1,1
  183.         SACL I        * I = I + N1
  184.         BANZ ZERO
  185. *
  186. * End of W = 0 butterfly.
  187. *
  188.         LARP 1
  189.         BANZ NORM    * If this is last phase,
  190.         B DRC4        * go to end.
  191. *****************************************************************
  192. *
  193. * Standard radix-4 butterfly.
  194. *
  195. *****************************************************************
  196. NORM         LAC  IE
  197.          SACL IA          * IA = IE
  198.          LARP 0
  199.          LAR  AR0,N2
  200.          MAR  *-
  201.          MAR  *-          * Loop for J = 1 to N2-1
  202.          LACK 1
  203.          SACL J
  204. JLOOP        SUB  JT
  205.         BZ   SPEC     * If J = JT, then use special butterfly.
  206. *
  207.         LAC  TABLE
  208.         ADD  IA
  209.         TBLR SI1      * Get twiddle factor 1
  210.         ADD  QUARTN
  211.         TBLR CO1
  212.         LAC  TABLE
  213.         ADD  IA,1
  214.         TBLR SI2      * Get twiddle factor 2
  215.         ADD  QUARTN
  216.         TBLR CO2
  217.         LAC  TABLE
  218.         ADD  IA,1
  219.         ADD  IA
  220.         TBLR SI3      * Get twiddle factor 3
  221.         ADD  QUARTN
  222.         TBLR CO3
  223.         LAC  IA
  224.         ADD  IE
  225.         SACL IA     * IA = IA + IE
  226.         LAC  J,1
  227.         SACL I        * I = J (data organized as real value followed
  228. *                * by imaginary so address I is 2 times J).
  229. ILOOP           LAC    I
  230.            ADD    N2,1
  231.            SACL I1        * I1 = I + N2
  232.            ADD    N2,1
  233.            SACL I2        * I2 = I1 + N2
  234.            ADD    N2,1
  235.            SACL I3        * I3 = I2 + N2
  236. *
  237.            OUT    I,PA0        * Output address of XI
  238.            IN    XI,PA1        * Read real and imaginary parts
  239.            IN    YI,PA1
  240.            OUT    I1,PA0         * Output address of XI1
  241.            IN    XI1,PA1      * Read real and imaginary parts
  242.            IN    YI1,PA1
  243.            OUT    I2,PA0         * Output address of XI2
  244.            IN    XI2,PA1      * Read real and imaginary parts
  245.            IN    YI2,PA1
  246.            OUT    I3,PA0         * Output address of XI3
  247.            IN    XI3,PA1      * Read real and imaginary parts
  248.            IN    YI3,PA1
  249. *
  250. * Compute butterfly.
  251. *
  252.            LAC    XI
  253.            ADD    XI2
  254.            SACL R1        * R1 = X(I) + X(I2)
  255.            SUB    XI2,1
  256.            SACL R2        * R2 = X(I) - X(I2)
  257.            LAC    XI1
  258.            ADD    XI3
  259.            SACL T        * T = X(I1) + X(I3)
  260.            ADD    R1
  261.            SACL XI        * X(I) = R1 + T
  262.            SUB    T,1
  263.            SACL R1        * R1 = R1 - T
  264.            LAC    YI
  265.            ADD    YI2
  266.            SACL S1        * S1 = Y(I) + Y(I2)
  267.            SUB    YI2,1
  268.            SACL S2        * S2 = Y(I) - Y(I2)
  269.            LAC    YI1
  270.            ADD    YI3
  271.            SACL T        * T = Y(I1) + Y(I3)
  272.            ADD    S1
  273.            SACL YI        * Y(I) = S1 + T
  274.            SUB    T,1
  275.            SACL S1        * S1 = S1 -T
  276. *
  277.            LT    CO2
  278.            MPY    S1
  279.            PAC
  280.            LT    SI2
  281.            MPY    R1
  282.            SPAC
  283.            SACH YI2,1        * Y(I2) = (S1*CO2) - (R1*SI2)
  284.            MPY    S1
  285.            PAC
  286.            LT    CO2
  287.            MPY    R1
  288.            LTA    CO1
  289.            SACH XI2,1        * X(I2) = (R1*CO2) + (SI*SI2)
  290. *
  291.            LAC    YI1
  292.            SUB    YI3
  293.            SACL T        * T = Y(I1) - Y(I3)
  294.            ADD    R2
  295.            SACL R1        * R1 = R2 + T
  296.            SUB    T,1
  297.            SACL R2        * R2 = R2 - T
  298.            LAC    XI1
  299.            SUB    XI3
  300.            SACL T        * T = X(I1) - X(I3)
  301.            LAC    S2
  302.            SUB    T
  303.            SACL S1        * S1 = S2 - T
  304.            ADD    T,1
  305.            SACL S2        * S2 = S2 + T
  306. ***
  307.            MPY    S1
  308.            PAC
  309.            LT    SI1
  310.            MPY    R1
  311.            SPAC
  312.            SACH YI1,1        * Y(I1) = (S1*CO1) - (R1*SI1)
  313.            MPY    S1
  314.            PAC
  315.            LT    CO1
  316.            MPY    R1
  317.            LTA    CO3
  318.            SACH XI1,1        * X(I1) = (R1*CO1) + (S1*SI1)
  319.            MPY    S2
  320.            PAC
  321.            LT    SI3
  322.            MPY    R2
  323.            SPAC
  324.            SACH YI3,1        * Y(I3) = (S2*CO3) - (R2*SI3)
  325.            MPY    S2
  326.            PAC
  327.            LT    CO3
  328.            MPY    R2
  329.            APAC
  330.            SACH XI3,1        * X(I3) = (R2*CO3) + (S2*SI3)
  331. *
  332. * Output results of the butterfly.
  333. *
  334.            OUT    I,PA0
  335.            OUT    XI,PA1
  336.            OUT    YI,PA1
  337.            OUT    I1,PA0
  338.            OUT    XI1,PA1
  339.            OUT    YI1,PA1
  340.            OUT    I2,PA0
  341.            OUT    XI2,PA1
  342.            OUT    YI2,PA1
  343.            OUT    I3,PA0
  344.            OUT    XI3,PA1
  345.            OUT    YI3,PA1
  346. *
  347. * Add increment for next loop.
  348. *
  349.            LAC    I
  350.            ADD    N1,1
  351.            SACL I        * I = I + N1
  352.            SUB    HOLDN,1
  353.            BLZ    ILOOP        * Loop while I < N
  354.            LAC  J
  355.            ADD  ONE
  356.            SACL J            * J = J + 1
  357.            BANZ JLOOP
  358.        LAC    IE,2
  359.        SACL IE            * IE = IE * 4
  360.        B    KLOOP
  361. ********************************************************************
  362. *
  363. *  Special routine for theta = pi/4.
  364. *
  365. ********************************************************************
  366. SPEC        LAC  J,1
  367.         SACL I            * I = J
  368. SLOOP        LAC  I
  369.         ADD  N2,1
  370.         SACL I1            * I1 = I + N2
  371.         ADD  N2,1
  372.         SACL I2            * I2 = I1 + N2
  373.         ADD  N2,1
  374.         SACL I3            * I3 = I2 +N2
  375. *
  376. * Input data values.
  377. *
  378.         OUT  I,PA0
  379.         IN     XI,PA1
  380.         IN     YI,PA1
  381.         OUT  I1,PA0
  382.         IN     XI1,PA1
  383.         IN     YI1,PA1
  384.         OUT  I2,PA0
  385.         IN     XI2,PA1
  386.         IN     YI2,PA1
  387.         OUT  I3,PA0
  388.         IN     XI3,PA1
  389.         IN     YI3,PA1
  390. *
  391. * Compute butterfly.
  392. *
  393.         LAC  XI
  394.         ADD  XI2
  395.         SACL R1        * R1 = X(I) + X(I2)
  396.         SUB  XI2,1
  397.         SACL R2        * R2 = X(I) - X(I2)
  398.         LAC  YI
  399.         ADD  YI2
  400.         SACL S1        * S1 = Y(I) + Y(I2)
  401.         SUB  YI2,1
  402.         SACL S2        * S2 = Y(I) - Y(I2)
  403.         LAC  XI1
  404.         ADD  XI3
  405. *                * T = X(I1) + X(I3)
  406.         ADD  R1
  407.         SACL XI        * X(I) = T + R1
  408.         SUB  R1,1
  409.         SACL YI2        * Y(I2) = T - R1
  410.         LAC  YI1
  411.         ADD  YI3
  412.         SACL T        * T = Y(I1) + Y(I3)
  413.         ADD  S1
  414.         SACL YI        * Y(I) = S1 + T
  415.         SUB  T,1
  416.         SACL XI2        * X(I2) = S1 - T
  417.         LAC  XI1
  418.         SUB  XI3
  419.         SACL R1        * R1 = X(I1) - X(I3)
  420.         LAC  YI1
  421.         SUB  YI3
  422.         SACL S1        * S1 = Y(I1) - Y(I3)
  423.         ADD  R2
  424.         SACL T        * T = R2 + S1
  425.         SUB  S1,1
  426.         SACL R2        * R2 = R2 - S1
  427.         LAC  S2
  428.         SUB  R1
  429.         SACL S1        * S1 = S2 - R1
  430.         ADD  R1,1
  431.         SACL S2        * S2 = S2 + R1
  432. *
  433.         LT     C21
  434.         MPY  S1
  435.         PAC
  436.         MPY  T
  437.         APAC
  438.         SACH XI1,1        * X(I1) = (T + S1) * C21
  439.         SPAC
  440.         SPAC
  441.         SACH YI1,1        * Y(I1) = (S1 - T) * C21
  442.         ZAC
  443.         MPY  R2
  444.         SPAC
  445.         MPY  S2
  446.         APAC
  447.         SACH XI3,1        * X(I3) = (S2 - R2) * C21
  448.         SPAC
  449.         SPAC
  450.         SACH YI3,1        * Y(I3) = -(S2 + R2) * C21
  451. *
  452. * Output results.
  453. *
  454.         OUT  I,PA0
  455.         OUT  XI,PA1
  456.         OUT  YI,PA1
  457.         OUT  I1,PA0
  458.         OUT  XI1,PA1
  459.         OUT  YI1,PA1
  460.         OUT  I2,PA0
  461.         OUT  XI2,PA1
  462.         OUT  YI2,PA1
  463.         OUT  I3,PA0
  464.         OUT  XI3,PA1
  465.         OUT  YI3,PA1
  466. *
  467.          LAC  I
  468.          ADD  N1,1
  469.          SACL I            * I = I + N1
  470.          SUB  HOLDN,1
  471.          BLZ  SLOOP         * Loop while I < N
  472.       LAC  J
  473.       ADD  ONE
  474.       SACL J            * J = J + 1
  475.       LAC  IA
  476.       ADD  IE
  477.       SACL IA            * IA = IA + IE
  478.       BANZ JLOOP
  479.   LAC  IE,2
  480.   SACL IE                * IE = IE * 4
  481.   B    KLOOP
  482. *
  483. * Digit reverse counter for radix-4 FFT computation.
  484. *
  485. DRC4    ZAC
  486.     SACL J
  487.     SACL I
  488.     LARP 0
  489.     LAR  AR0,HOLDN
  490.     MAR  *-
  491.     MAR  *-
  492. DRLOOP        SUB  J
  493.         BGEZ NOSWAP
  494. * Swap I and J values.
  495.             OUT  I,PA0
  496.             IN   XI,PA1
  497.             IN   YI,PA1
  498.             OUT  J,PA0
  499.             IN   XJ,PA1
  500.             IN   YJ,PA1
  501.             OUT  J,PA0
  502.             OUT  XI,PA1
  503.             OUT  YI,PA1
  504.             OUT  I,PA0
  505.             OUT  XJ,PA1
  506.             OUT  YJ,PA1
  507. *
  508. NOSWAP        LAC  QUARTN,1
  509.         SACL K
  510. INLOOP            LT   K
  511.             MPYK 3
  512.             PAC
  513.             SACL TEMP
  514.             SUB  J
  515.             BGZ  OUTL
  516.                 LAC  J
  517.                 SUB  TEMP
  518.                 SACL J
  519.                 LAC  K,14
  520.                 SACH K
  521.                 B    INLOOP
  522. OUTL        LAC  J
  523.         ADD  K
  524.         SACL J
  525.         LAC  I
  526.         ADD  ONE,1
  527.         SACL I
  528.         BANZ DRLOOP
  529. *
  530. * End of FFT
  531. *
  532. STOP    B STOP
  533. *
  534. * Twiddle factor for theta = pi/4.
  535. *
  536. COS21 DATA 23169
  537. *
  538. * Sine and cosine table.
  539. *
  540. SINE  EQU $
  541.       DATA 0
  542.       DATA 3211
  543.       DATA 6392
  544.       DATA 9511
  545.       DATA 12539
  546.       DATA 15446
  547.       DATA 18204
  548.       DATA 20787
  549.       DATA 23169
  550.       DATA 25329
  551.       DATA 27244
  552.       DATA 28897
  553.       DATA 30272
  554.       DATA 31356
  555.       DATA 32137
  556.       DATA 32609
  557. COSINE EQU $
  558.       DATA 32767
  559.       DATA 32609
  560.       DATA 32137
  561.       DATA 31356
  562.       DATA 30272
  563.       DATA 28897
  564.       DATA 27244
  565.       DATA 25329
  566.       DATA 23169
  567.       DATA 20787
  568.       DATA 18204
  569.       DATA 15446
  570.       DATA 12539
  571.       DATA 9511
  572.       DATA 6392
  573.       DATA 3211
  574.       DATA 0
  575.       DATA -3211
  576.       DATA -6392
  577.       DATA -9511
  578.       DATA -12539
  579.       DATA -15446
  580.       DATA -18204
  581.       DATA -20787
  582.       DATA -23169
  583.       DATA -25329
  584.       DATA -27244
  585.       DATA -28897
  586.       DATA -30272
  587.       DATA -31356
  588.       DATA -32137
  589.       DATA -32609
  590.       DATA -32767
  591.       DATA -32609
  592.       DATA -32137
  593.       DATA -31356
  594.       DATA -30272
  595.       DATA -28897
  596.       DATA -27244
  597.       DATA -25329
  598.       DATA -23169
  599.       DATA -20787
  600.       DATA -18204
  601.       DATA -15446
  602.       DATA -12539
  603.       DATA -9511
  604.       DATA -6392
  605.       DATA -3211
  606.       END
  607.